import itertools as it
import pprint as pp

def hamiltonian_cycle(matrix):
    poss = dict()
    n = len(matrix)
    start = matrix[0][0]

    for subset_len in range(1, n + 1):
        for subset in it.combinations(range(n), subset_len):
            poss[subset] = dict()
            for vertex in subset:
                if start not in subset:
                    continue

                if subset_len == 1:
                    poss[subset][start] = True
                    continue

                if vertex == start:
                    continue

                # get the neighbors
                from_neighbors = []
                for i in range(n):
                    if matrix[i][vertex] and i in subset:
                        from_neighbors.append(i)

                # create S-v
                new_subset = tuple(node for node in subset if node != vertex)

                # test if any of the neighbors were possible
                good = False
                for neighbor in from_neighbors:
                    if new_subset in poss and neighbor in poss[new_subset] and poss[new_subset][neighbor]:
                        good = True
                        break
                poss[subset][vertex] = good
    pp.pprint(poss)

    all = tuple(range(n))
    for node in poss[all]:
        if poss[all][node]:
            return True
    return False
if __name__ == '__main__':
    matrix = [
        [0, 1, 0, 0, 1],
        [0, 0, 1, 0, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 1],
        [1, 0, 0, 0, 0]
    ]

    print(hamiltonian_cycle(matrix))
